package com.jm.offer.easy;

import com.jm.offer.ListNode;
import jdk.nashorn.internal.runtime.UnwarrantedOptimismException;

/**
 * @Description https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/
 * @date 2022/4/15 7:46
 */
public class _25合并两个排序的链表 {
    public static void main(String[] args) {
        ListNode l1 = new ListNode(1,new ListNode(2, new ListNode(3,new ListNode(4))));
        ListNode l2 = new ListNode(1,new ListNode(4, new ListNode(5,new ListNode(6))));
        // 1 1 2 3 4 5 6
        ListNode.printLinkedList(mergeTwoLists(l1,l2));
        System.out.println("-0--");
        ListNode.printLinkedList(ListNode.createLinkedListByRandom(10));
    }

    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 声明一个哨兵节点，便于返回
        ListNode preHead = new ListNode(-1);
        // 前驱节点
        ListNode prev = preHead;
        while (l1 != null && l2 != null){
            // 判断l1 和 l2 的大小，小的作为prev的next并指向当前链表的下一个，大的不做处理。
            if (l1.val <= l2.val){
                prev.next = l1;
                l1 = l1.next;
            }else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }
        prev.next = l1 == null ? l2 : l1;
        return preHead.next;
    }
}
